﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Compilex.Automata;
using Infraestruturex.BaseLibrary;
using Compilex.BaseLibrary;

namespace Infraestruturex
{
    using Partition = HashSet<DFAState>;

    public class DFAMinimizer
    {
        public DFA DFA{ get; private set; }
        public DFA MinimalDFA { get; set; }
        private HashSet<DFAState> states;
        private HashSet<string> alphabet;
        private HashSet<Partition> partitions = new HashSet<Partition>();
        private DFAState deadState =  null;

        public DFAMinimizer(DFA dfa)
        {
            this.DFA = dfa;
            this.states = new HashSet<DFAState>(dfa.GetStates());
            this.alphabet = GetAlphabet();
            deadState = AddDeadState();

            Partition finalStates = new Partition(states.Where(s => s.IsAcceptState));
            Partition notFinalStates = new Partition(states.Where(s => !s.IsAcceptState));

            partitions.Add(finalStates);
            partitions.Add(notFinalStates);
        }

        public DFA Minimize()
        {
            int oldPartitionCount;
            do
            {
                oldPartitionCount = partitions.Count;
                RefinePartitions();
            }
            while (partitions.Count > oldPartitionCount);

            HashSet<DFAState> minimizedStates = new HashSet<DFAState>();
            partitions.ForEach(p => minimizedStates.Add(p.First()));
            MinimalDFA = new DFA();
            foreach (DFAState state in minimizedStates)
            {
                Partition containingPartition = partitions.Where(p => p.Contains(state)).First();
                string name = "{";
                containingPartition.ForEach(s => name += s.Name + ", ");
                name = name.Substring(0, name.Length - 2);
                name += "}";
                state.Name = name;

                // vê se é inicial
                if (containingPartition.Contains(DFA.StartState))
                {
                    MinimalDFA.StartState = state;
                }
                // faz as transições
                List<SimpleTransitionRule<DFAState>> newTransitions =
                    new List<SimpleTransitionRule<DFAState>>();
                

                foreach (var transition in state.Transitions.ToArray())
                {
                    if (transition.Destination != deadState)
                    {
                        newTransitions.Add(new SimpleTransitionRule<DFAState>(
                            ((SimpleTransitionRule<DFAState>)transition).Input,
                            partitions.Where(p => p.Contains(transition.Destination)).First().First()));
                    }
                }

                state.Transitions = new SimpleList<ITransitionRule<DFAState>>();
                newTransitions.ForEach(t => state.Transitions.Add(t));
            }

            //RemoveDeadState(minimizedStates);
            return MinimalDFA;

        }

        //private void RemoveDeadState(HashSet<DFAState> minimizedStates)
        //{
        //    foreach (DFAState state in minimizedStates)
        //    {
        //        SimpleList<ITransitionRule<DFAState>> newTransitions;
        //        foreach (var transition in state.Transitions.ToArray())
        //        {
        //            if (transition.Destination.Name == "DeadState")
        //            {
        //                state.Transitions.Re
        //            }
        //        }
        //    }
        //}



        private void RefinePartitions()
        {
            foreach (string symbol in alphabet)
            {
                var newPartitions = new HashSet<Partition>();
                foreach (Partition partition in partitions)
                {
                    Dictionary<Partition, Partition> partitionsMap =
                        new Dictionary<Partition,Partition>();
                    foreach (DFAState state in partition)
                    {
                        Partition destinationPartition = GetPartitionByState((
                            from transition in state.Transitions.ToArray()
                                where transition.MatchesInput(symbol)
                                select transition.Destination).First());

                        if (!partitionsMap.ContainsKey(destinationPartition))
                        {
                            partitionsMap.Add(destinationPartition, new Partition());
                        }
                        partitionsMap[destinationPartition].Add(state);
                    }
                    partitionsMap.ForEach(kvp => newPartitions.Add(kvp.Value));
                }
                partitions = newPartitions;
            }
        }

        private Partition GetPartitionByState(DFAState state)
        {
            return partitions.Where(p => p.Contains(state)).First();
        }

        private HashSet<string> GetAlphabet()
        {
            HashSet<string> alphabet = new HashSet<string>();
            foreach (DFAState state in states)
            {
                for (int i = 0; i < state.Transitions.Count; i++)
                {
                    ITransitionRule<DFAState> transition = state.Transitions[i];
                    if (transition is SimpleTransitionRule<DFAState>)
                    {
                        SimpleTransitionRule<DFAState> simpleTransition =
                            (SimpleTransitionRule<DFAState>)transition;
                        alphabet.Add(simpleTransition.Input);
                    }
                }
            }
            return alphabet;
        }

        private DFAState AddDeadState()
        {
            DFAState deadState = new DFAState("DeadState");
            alphabet.ForEach(symbol => deadState.AddTransition(symbol, deadState));
            bool deadStateNeeded = false;
            foreach (DFAState state in states)
            {
                foreach (string symbol in alphabet)
                {
                    bool hasTransition = (from t in state.Transitions.ToArray()
                                         where t is SimpleTransitionRule<DFAState> &&
                                           ((SimpleTransitionRule<DFAState>) t).Input == symbol
                                          select t).Count() > 0;
                    if (!hasTransition)
                    {
                        state.AddTransition(symbol, deadState);
                        deadStateNeeded = true;
                    }

                }
            }

            if (deadStateNeeded)
            {
                states.Add(deadState);
                return deadState;
            }
            else
            {
                return null;
            }
        }

    }
}
